package summary;

import java.util.*;

/**
 * @Author: 海琳琦
 * @Date: 2022/4/19 20:21
 * https://leetcode-cn.com/problems/bus-routes/
 */
public class Title815 {

    public static int numBusesToDestination(int[][] routes, int source, int target) {
        //初始==终点，不上公交车
        if (source == target) {
            return 0;
        }
        //判断车站属于那个公交路线
        Map<Integer, List<Integer>> graph = new HashMap<>();
        //判断公交车站所在的线路经过的公交线路的长度，也用于判断经过的路线是否重复
        Map<Integer, Integer> steps = new HashMap<>();
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < routes.length; i++) {
            for (Integer station : routes[i]) {
                if (station == source) {
                    queue.offer(i);
                    steps.put(i, 1);
                }
                graph.computeIfAbsent(station, k -> new ArrayList<>()).add(i);
            }
        }
        //从一条路线出发，到另一条路线；判断另一条路线上是否有目的地，有的话返回经过的路线个数
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                //当前的公交车线路
                Integer route = queue.poll();
                Integer step = steps.get(route);
                for (Integer station : routes[route]) {
                    if (station == target) {
                        return step;
                    }
                    //将由该线路的车站发起的路线，加入队列
                    List<Integer> lines = graph.get(station);
                    for (Integer line : lines) {
                        if (!steps.containsKey(line)) {
                            steps.put(line, step + 1);
                            queue.offer(line);
                        }
                    }
                }
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        int[][] routes = {{1, 2, 7}, {3, 6, 7}};
        numBusesToDestination(routes, 1, 6);
    }
}
